#!/usr/bin/python

#### PYTHONICA PARSER / UNPARSER ####

#Immediate TODO's:
####1) TEST the line with #>>> (currently 397).. Do this through pythonicaTEST.py.  Also, rename that file :-/
#   2) Have the interactive CLI work better, i.e. up arrow gives previous entry. Build non-interactive CLI
#   3) Set up a real debugging system.

import sys, string, re, types
from pythonicacore import *

gEntryNum = 1
gSymToName = {}
gNameToSym = {}
gNameToPrec = {}
gNonchainable = ('ReplaceAll','Rule','Power','Divide','Minus') #took out 'Times'
gUnary = ('Minus')
# note: instead of just "nonchainable", we should note whether
# each function groups left, groups right, or chains
# (compare -> and /. in Mathematica; right and left, resp.)

#Used to print debug info.. it prints out A LOT.
verbose = False

#----------------------------------------------------------------------
def buildOperTables():
    global gSymToName, gNameToPrec, gNameToSym   
    gSymToName['/.'] = 'ReplaceAll'
    gSymToName['->'] = 'Rule'
    gSymToName['|'] = 'Or'
    gSymToName['~'] = 'Xor' #If someone knows a better char for xor, speak up!
    gSymToName['&'] = 'And'
    gSymToName['>'] = 'GreaterThan'
    gSymToName['<'] = 'LessThan'
    gSymToName['<='] = 'LessOrEqualTo'
    gSymToName['>='] = 'GreaterOrEqualTo'
    gSymToName['!='] = 'NotEqual'
    gSymToName['=='] = 'Equal'
    gSymToName['='] = 'Set'
    gSymToName['=.'] = 'Unset'
    gSymToName['+'] = 'Plus'
    gSymToName['-'] = 'Minus'
    gSymToName['*'] = 'Times'
    gSymToName['/'] = 'Divide'
    gSymToName['^'] = 'Power'
    
    gNameToSym['ReplaceAll'] = '/.'
    gNameToSym['Rule'] = '->'
    gNameToSym['Or'] = '|'
    gNameToSym['Xor'] = '~'
    gNameToSym['And'] = '&'
    gNameToSym['GreaterThan'] = '>'
    gNameToSym['LessThan'] = '<'
    gNameToSym['LessOrEqualTo'] = '<='
    gNameToSym['GreaterOrEqualTo'] = '>='
    gNameToSym['NotEqual'] = '!='
    gNameToSym['Equal'] = '=='
    gNameToSym['Set'] = '='
    gNameToSym['Unset'] = '=.'
    gNameToSym['Plus'] = '+'
    gNameToSym['Minus'] = '-'
    gNameToSym['Times'] = '*'
    gNameToSym['Divide'] = '/'
    gNameToSym['Power'] = '^'
    
    gNameToPrec['ReplaceAll'] = 0
    gNameToPrec['Rule'] = 1
    gNameToPrec['Or'] = 2
    gNameToPrec['Xor'] = 2
    gNameToPrec['And'] = 3
    gNameToPrec['GreaterThan'] = 4
    gNameToPrec['LessThan'] = 4
    gNameToPrec['LessOrEqualTo'] = 4
    gNameToPrec['GreaterOrEqualTo'] = 4
    gNameToPrec['NotEqual'] = 4
    gNameToPrec['Equal'] = 4
    gNameToPrec['Set'] = 5
    gNameToPrec['Unset'] = 6
    gNameToPrec['Plus'] = 7
    gNameToPrec['Minus'] = 7
    gNameToPrec['Times'] = 8
    gNameToPrec['Divide'] = 9
    gNameToPrec['Power'] = 10

buildOperTables()

#----------------------------------------------------------------------
def endOfExpr(s):
    """ return the position at which this token ends.
    it may be delimited by a delimiter, or the end of the string
    The token ends at an operator, the end of a [..], or (..)"""
    p = 0
    maxp = len(s)
    while p < maxp:
        # check for non-alphanumeric chars
        if not s[p].isalnum() and s[p] not in ['[','(','.']:
            return p
        # check for groupings...
        if s[p] == '[':                 # if we start a '[...]',
            # return if it's a slice
            if p > 0 and s[p+1] == '[':
                return p
            nest = 1
            while nest:                 # ...finish it
                p += 1
                if s[p] == '[': nest += 1
                if s[p] == ']': nest -= 1
            return p + 1
        if s[p] == '(':                 # if we start a '(...)',
            if p == 0:                  # Make sure we're at the beginning of the string
                nest = 1
                while nest:             # ...finish it
                    p = p + 1
                    if s[p] == '(': nest = nest + 1
                    if s[p] == ')': nest = nest - 1
                return p + 1
            else:
                # We're in the middle of the string. End the token now.
                return p
        p += 1
    return p

#----------------------------------------------------------------------
def endOfArg(s):
    """ returns the position where this argument ends
    an argument ends on a comma or end of string, ignoring commas in groups"""
    p = 0
    maxp = len(s)
    while p < maxp:
        if s[p] == ',':
            return p
        if s[p] == '[':
            nest = 1
            while nest:
                p += 1
                if s[p] == '[': nest += 1
                if s[p] == ']': nest -= 1
        if s[p] == '(':
            nest = 1
            while nest:
                p += 1
                if s[p] == '(': nest += 1
                if s[p] == ')': nest -= 1
        p += 1
    return p

#----------------------------------------------------------------------
def splitExprs(s):
    """ split on delimiters, ignoring those nested in [..] or (..)
    e.g. -23+5*(3-6.0)+10 would have
    outexpr  = ['', '23', '5', '(3-6.0)', '10'] and
    outdelim = ['-', '+', '*', '+', ''].
    It would then be later broken so that outexpr = ['3', '6.0']
    and outdelim = ['-', '']"""
    outexpr = []
    outdelim = []
    while s:
        end = endOfExpr(s)
        outexpr.append(s[:end])
        if end >= len(s):
            outdelim.append('')
        elif s[end:end+2] in ['[[',']]']:
            outdelim.append(s[end])
        elif s[end:end+2] in gSymToName.keys():
            outdelim.append(s[end:end+2])
        elif s[end] in gSymToName.keys():
            outdelim.append(s[end])
        elif not s[end].isalnum():
            outdelim.append(s[end])
        else:
            outdelim.append('*')
            end -= 1
        s = s[end+len(outdelim[-1]):]
    return outexpr,outdelim

#----------------------------------------------------------------------
def splitArgs(s):
    """ split arguments - split on commas, skipping groups"""
    outexpr = []
    while s:
        end = endOfArg(s)
        outexpr.append(s[:end])
        s = s[end+1:]
    return outexpr

#----------------------------------------------------------------------
# Get rid of this so the % sign can do modulus.  Repalace ans, ans(1) with
# Out[-1], ans(2) with Out[-2], etc.
def subPercent(s):
    """ subPercent(s): replace one '%' with Out[-1],
    '%%' with the Out[-2], etc., and %n (where n is
    an integer) with the Out[n]."""
    while 1:
        l = len(s)
        pos = s.find('%')
        if pos < 0: return s
        cnt = 1
        while pos+cnt < l and s[pos+cnt] in '%0123456789':
            cnt = cnt+1
        substr = s[pos:pos+cnt]
        if len(substr) > 1 and substr[1] != '%':
            rep = 'Out[' + substr[1:] + ']'
        else:
            rep = 'Out[-' + str(len(substr)) + ']'
        s = s[:pos] + rep + s[pos+cnt:]

#----------------------------------------------------------------------
# I don't really need this since I've already implimented implicit multiplication.
def stripSpaces(s):
    """ stripSpaces(s): strip all spaces from the input string,
    except that if a space occurs between any combination of
    numbers and symbols, convert it to '*'."""
    out = ''
    hadsym = 0      # flag: did we just have a symbol or number?
    hadspace = 1    # flag: did we just have some whitespace?
    symchars = string.letters + string.digits
    for c in s:
        if c != ' ':
            if hadspace:
                # we just had a space...
                if c in symchars:
                    # and now we see a symbol
                    # if we had a symbol before that, throw in a '*'
                    if hadsym: out = out + '*'
            hadsym = (c in symchars)
            out = out + c
            hadspace = 0
        else:
            hadspace = 1
    return out

#----------------------------------------------------------------------
def isNumber(s):
    """ detect if s is a number - allows negative sign and a single period"""
    if len(s) == 0:
        return False
    if s[0] == '-': s = s[1:]
    if s.find('.') != s.rfind('.'):
        # too many periods
        return False
    for char in s:
        if char not in "0123456789.":
            return False
    return True

#----------------------------------------------------------------------
def parseOneExpr(s):
    """ parseOneExpr(s): build one token from the string s.
    This string should immediately be a token, and contain no
    paretheses, operators, etc., except within arguments.
    Returns object ExprNumber() if the token is a number,
    ExprFunction() if we have a function (where Function in
    ExprFunction is sin, cos, log, etc.).  Could also return
    Expr objects for Complex, Symbol, or List."""
    wip = []
    # get first token
    #I think the re.search() is finding the first place
    #   a left brace, right brace, comma, or space occurs.
    #   PLEASE correct this statement if it's wrong.
    delim = re.search(r'[][, ]', s)
    if not delim:
        delim = -1
        token = s
        delimchar = '\n'
    else:
        delim = delim.span()[0]
        token = s[:delim]
        delimchar = s[delim]
    expr = None
    
    # do we have a FullForm expression (Head[args], e.g. log[128,2])?
    if delimchar == '[':
        # check for a list
        if token == '':
            expr = ExprList()
        else:
            # check for a built-in symbol; otherwise, use ExprSymbol
            try: expr = eval('Expr' + token + '()' )
            except: expr = Expr([],token)
        # ...find all the elements for this expression
        estr = s[:endOfExpr(s)+1]
        estr = estr[delim+1:-1]
        estrlist = splitArgs(estr)
        expr.setData(map(parse, estrlist))

    # if not, then do we have a number?
    elif isNumber(token):
        # A number...
        expr = ExprNumber(float(token))
    
    # if not, do we have a complex number?
    elif token[-1] == 'j' and (len(token) == 1 or isNumber(token[:-1])):
        # A complex number...
        if len(token) == 1:
            expr = ExprComplex((0,1))
        else:
            expr = ExprComplex((0,float(token[:-1])))

    # if neither of those, then it must be a symbol
    else:
        # a Symbol...
        # Symbols can't start with numbers, tho
        if token[0].isdigit() or (token[0] == '-' and token[1].isdigit()):
            raise "Symbol::parse", "Symbols can't start with a digit."
        expr = ExprSymbol(token)
    return expr

#----------------------------------------------------------------------
def parse(s):
    global gSymToName, gNameToPrec, gNonchainable, verbose

    #split into tokens... 
    #  estrlist contains the numbers, 
    #  delimlist contains the operators
    estrlist,delimlist = splitExprs(s)
    if verbose: print "estrlist: " + str(estrlist) + "\ndelimlist: " + str(delimlist)

    # crawl through tokens, combining where operators are found
    wip = []  # stack of expressions

    # evaluate each token, considering its following delimiter
    for i in range(0,len(estrlist)):
        if verbose: print "__________  " + str(i) + "  ____________"
        if estrlist[i]:
            if estrlist[i][0] == '(':
                # if we have parentheses, parse their contents!
                expr = parse(estrlist[i][1:-1])
            else:
                # otherwise, load a single expression (Expr object)
                expr = parseOneExpr(estrlist[i])
        else: expr = None
        if verbose: print "expr: " + tostr(expr)
        if delimlist[i] in gSymToName.keys():
            # we have an operator...
            opername = gSymToName[delimlist[i]]
            if verbose: print "opername: " + tostr(opername)
            try:
                operclass = eval('Expr' + opername)
            except:
                raise "Bug", "Undefined operator " + opername

            if not wip:
                # first expression we've seen; throw it on the stack
                wip.append(operclass(expr))
                if verbose: print "First wip: " + tostr(wip)

            elif not wip[-1].Head():
                # current expression is headless -- make it us
                wip[-1].head = opername
                if expr: wip[-1].data.append(expr)
                if verbose: print "Wip with Head: " + tostr(wip)

            elif wip[-1].Head() == opername and opername not in gNonchainable:
                # same operator; append to previous data
                wip[-1].data.append(expr)
                if verbose: print "Data appended: "

            else:
                # figure out where to stuff token,
                # according to precedence rules
                myPrecedence = gNameToPrec[opername]
                curPrecedence = gNameToPrec[wip[-1].Head()]
                if verbose: print "myPrec: " + str(myPrecedence) + ", curPrec: " + str(curPrecedence)
                if curPrecedence < myPrecedence:
                    # current head has lower precedence... start a new level
                    if verbose: print opername, "higher than", wip[-1].Head()
                    wip.append(operclass(expr))
                    if verbose: print "Higher wip: " + tostr(wip)
                    wip[-2].data.append(wip[-1])
                    if verbose: print "Not sure wip: " + tostr(wip)
                else:
                    # current head has higher precedence...
                    # add expr to current, then move it within us
                    if verbose: print opername, "lower than", wip[-1].Head()
                    if expr: wip[-1].data.append(expr)
                    if verbose: print "Low, Expr append wip: " + tostr(wip)
                    which = len(wip)-2
                    while which >= 0:
                        if gNameToPrec[ wip[which].Head() ] >= myPrecedence:
                            if verbose: print "...lower than", wip[which].Head()
                            pass
                        else:
                            if verbose: print "...but not lower than", wip[which].Head()
                            break
                        which -= 1
                    which += 1 # we want to wrap around one level higher
                    if verbose: print "Stuffing around wip: " + str(which) + ", wip[which]: " + tostr(wip[which])
                    if wip[which].Head() != opername or opername in gNonchainable:
                        if which == 0:
                            wip[0] = operclass(wip[0])
                            del wip[1:]
                            if verbose: print str(operclass) + "(wip[0]), del wip[1:].  wip = " + tostr(wip)
                        else:
                            wip[which-1].data[-1] = operclass(wip[which-1].data[-1])
                            wip[which] = wip[which-1].data[-1]
                            #del wip[which+1:] #>>> TEST THIS LINE AS MUCH AS POSSIBLE -- it might be a valid fix for the -3/2^1*4 problem
                            if verbose: print "Expr(wip[which-1].data[-1]), wip[which]=... . wip = " + tostr(wip)
                    else:
                        # get rid of wip entries above which
                        del wip[which+1:]
        elif delimlist[i] == '[':
            # we have a slice
            expr = ExprSlice(expr)
            if wip:
                wip[-1].data.append(expr)
            wip.append(expr)
        elif delimlist[i] == ']':
            # end of slice
            args = parse(estrlist[i])
            if args.Head() != 'List': # this should never happen
                raise 'parse::syntax', "Syntax error after token '%s'." % estrlist[i]
            wip[-1].data.append(args.data)
        elif delimlist[i] == '':
            if not wip:
                wip.append(expr)
                if verbose: print "End s, no wip: " + tostr(wip)
            else:
                if verbose: print "End s, wip[-1]: " + tostr(wip[-1])
                if verbose: print "Appending " + tostr(expr) + " into " + tostr(wip[-1].data)
                wip[-1].data.append(expr)
                if verbose: print "End s, with wip: " + tostr(wip)
        else:
            raise "parse::operators", "Undefined operator '%s'." % delimlist[i]
        if verbose: print "wip:", tostr(wip)
    if len(wip) >= 1:
        return wip[0]
    else:
        return None

#----------------------------------------------------------------------
def unparse(expr, leftprec=-1, rightprec=-1, depth=0):
    global gNameToSym, gNameToPrec, gSymToName, gUnary, verbose
    # is this expression something we have an operator for?
    head = expr.Head()
    if verbose: print "Unparse expr: " + tostr(expr) + ", Head: " + head
    if head not in gNameToPrec.keys():
        # nope, no operator... just print normally
        out = str(expr)
        if verbose: print "NO OPERATOR: RETURN"
        return out
    # yep, we have an operator... get it, and its precedence
    prec = gNameToPrec[head]
    if verbose: print "Precedence: " + str(prec)
    op = gNameToSym[head]
    # combine data using operator -- pass precedence info
    out = ''
    # leftmost argument gets has our left, and us for the right
    if verbose: print "Length of data: " + str(len(expr.data))
    if len(expr.data) > 0:
        if len(expr.data) == 1: r = rightprec
        else: r = prec
        if verbose: print "IN " + str(depth+1) + ":  len > 0"
        out = unparse(expr.data[0],leftprec,r,depth+1)
        if verbose: print "OUT " + str(depth+1) + ":  out is " + tostr(out)
        if len(expr.data) == 1 and head in gUnary: out = gNameToSym[head] + out
    # middle arguments have us on both left and right
    if len(expr.data) > 2:
        if verbose: print "IN " + str(depth+1) + ":  len > 2"
        out = out + op + \
                op.join(map(lambda x,p=prec:unparse(x,p,p,depth+1),expr.data[1:-1]))
        if verbose: print "OUT " + str(depth+1) + ":  out is " + tostr(out)
    # last argument has our right, and us for the left
    if len(expr.data) > 1:
        if verbose: print "IN " + str(depth+1) + ":  len > 1"
        out = out + op + unparse(expr.data[-1],prec,rightprec,depth+1)
        if verbose: print "OUT " + str(depth+1) + ":  out is " + tostr(out)
    # use parenthesis if we're lower precedence than our neighbors
    if prec < leftprec or prec < rightprec:
        if verbose: print "  >surrounding " + out + " with parens"
        out = '(' + out + ')'
    if verbose: print "Returning " + out
    return out

#----------------------------------------------------------------------
def handleInput(s, printOutput=0):
    """ handleInput(s, printOutput=1): handle the given input,
    generating output if the second parameter is 1.  Return a
    tuple of (input-expr, output-expr)."""
    s = stripSpaces(subPercent(s))
    if s:
        inexp = parse(s)
        if inexp != None:
            evaluated = inexp.Eval()
            if printOutput:
                print
                print "in FullForm:", inexp
                print "evaluates to:", evaluated
                print "Unparsed FullForm: " + str(unparse(inexp))
            simp = evaluated.Simplify()
            while simp != evaluated:
                if printOutput: print "simplifies to:", simp
                evaluated = simp
                simp = evaluated.Simplify()
            return inexp,simp
    return None,None

#----------------------------------------------------------------------
def tostr(x):
    t = type(x)
    if t == types.DictionaryType:
        return '{' + string.join( \
            map( lambda k,d=x: tostr(k)+": "+tostr(d[k]), \
            x.keys() ), ", " ) + "}"
    if t == types.ListType:
        return '[' + string.join( \
            map( lambda i: tostr(i), x), \
            ", " ) + "]"
    if t == types.TupleType:
        if len(x) == 1: return '(' + tostr(x[0]) + ",)"
        return '(' + string.join( \
            map( lambda i: tostr(i), x), \
            ", " ) + ")"
    return str(x)

#----------------------------------------------------------------------
def mainLoop():
    global gEntryNum
    s = 'foo'
    while s:
        inexp = None
        outexp = None
        try:
            numstr = '[' + str(gEntryNum) + ']'
            s = raw_input("In" + numstr + " :=   ")
            # break on ';' and surpress output for all but the last
            commands = s.split(";")
            for c in commands[:-1]:
                inexp,outexp = handleInput(c,0)
            # on the last one, don't surpress output
            if commands[-1]:
                inexp,outexp = handleInput(commands[-1],1)
                if outexp:
                    print "outexp: " + str(outexp)
                    print
                    print "Out" + numstr, "=  ", unparse(outexp)
        except EOFError:
            raise
        except:
            # only display the message and keep going if this is the main module
            info = sys.exc_info()
            if __name__ == '__main__':
                if not isinstance(info[0], types.ClassType):
                    print "%s: %s" % info[:2]
                else:
                    print "Syntax Error"
            else:
                raise
        print
        
        # Turn the inexp/outexp into a None expression if they're None
        if inexp == None:
            inexp = Expr()
        if outexp == None:
            outexp = Expr()
        # store the in/out data for future reference
        StoreInOut( inexp,outexp )
        gEntryNum = gEntryNum + 1

#----------------------------------------------------------------------
if __name__ == '__main__':
    try:
        mainLoop()
        raw_input("Press Return.")
    except EOFError:
        print "" # print a newline
